package com.快速排序;

import java.util.Arrays;
import java.util.Set;

public class Solution {

	public static void quicksort(int a[], int low, int high) {
		if (low > high)
			return;
		int core = a[low];// 设置基准
		int i = low, j = high;
		while (i < j) {
			while (j > i && a[j] >=core) {
				j--;
			}
			while (i < j && a[i] <= core) {
				i++;
			}
			if (i < j) {
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}

		a[low] = a[i];
		a[i] = core;
		System.out.println(Arrays.toString(a));
		System.out.println("===========");
		quicksort(a, low, i - 1);
		quicksort(a, i + 1, high);
	}
	public static void quicksort1(int a[],int low,int high) {
		if(low>high)return;
		int i=low;
		int j=high;
		int core=a[low];
		while(i<j) {
			while(i<j&&a[j]>=core) {//一定要记住是>=符号，不能忘记
				j--;
			}
			while(i<j&&a[i]<=core) {
				i++;
			}
			if(i<j) {
				int temp=a[j];
				a[j]=a[i];
				a[i]=temp;
			}
		}
		//将基准的值交换
		a[low]=a[i];
		a[i]=core;
		quicksort1(a,low,i-1);
		quicksort1(a,i+1,high);
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	public static void quicksort2(int a[],int low,int high) {
		if(low>high)return;//递归退出的条件一定不能忘记
		int i=low;
		int j=high;
		int core = a[low];
		while(i<j) {
			while(i<j&&a[j]>=core) {
				j--;
			}
			while(i<j&&a[i]<=core) {
				i++;
			}
			if(i<j) {
				int temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
			
		}
		//排序完成一轮，将基准与i交换
		a[low] = a[i];
		a[i]=core;
		quicksort2(a,low,i-1);
		quicksort2(a,i+1,high);
	}
	
	
	
    

}
